package algorithm.dynamic_planning.leetcode;

/**
 * @author yuisama
 * @date 2022/12/05 12:16
 * 入门dp问题 - 凑零钱
 * 最优子结构
 * 原问题为 凑出amount = 11的金额最少需要多少硬币
 * 子问题 : 若知道凑出amount = 10,9,6的金额需要的硬币数，只需要 + 1硬币(再选出一枚5,2,1金额的硬币)即可得到原问题的解
 * 且子问题之间相互独立不影响
 **/
public class Num322_CoinInChange {
    // 1.暴力搜索 + 备忘录
//    int[] memo;
//    public int coinChange(int[] coins, int amount) {
//        // dp(amount)的解
//        // 在coins硬币中，凑出amount金额最少需要多少枚硬币
//        memo = new int[amount + 1];
//        // 初始化
//        Arrays.fill(memo,-100);
//        return dp(coins,amount);
//    }
//    /**
//     * 在coins硬币中凑出amount金额，最少需要的硬币数
//     * @param coins
//     * @param amount
//     * @return
//     */
//    private int dp(int[] coins, int amount) {
//        int res = Integer.MAX_VALUE;
//        // 1.base case
//        if (amount < 0) return -1;
//        if (amount == 0) return 0;
//        if (memo[amount] != -100) {
//            return memo[amount];
//        }
//        for (int coin : coins) {
//            // 选择当前硬币后，剩下的金额交给子函数
//            int childRes = dp(coins,amount - coin);
//            if (childRes == -1) {
//                // 子问题不存在解，跳过，说明当前选择无效
//                continue;
//            }
//            // 子问题有效，不断搜索最优解
//            res = Math.min(res,1 + childRes);
//        }
//        // 存储当前金额备忘录
//        // 当amount > coins时，没有解，此时选择任何硬币都是-1，返回此时对应金额的解为-1(此时res仍为MAX_VALUE)
//        memo[amount] = (res == Integer.MAX_VALUE ? -1 : res);
//        return memo[amount];
//    }
    // dp数组
    // dp[i]语义 : 凑出金额为i，最少需要dp[i]枚硬币
    public int coinChange(int[] coins, int amount) {
        // 1.base case
        if (amount < 0 ) return -1;
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        // 从子问题开始到原问题,i为金额数
        for (int i = 1; i <= amount; i++) {
            // 进行选择
            int res = Integer.MAX_VALUE;
            for (int coin : coins) {
                // 选择当前硬币后，子问题的解
                if (i - coin < 0) {
                    // 不存在解
                    continue;
                }
                int childNum = dp[i - coin];
                if (childNum == -1) {
                    // 当前选项的子问题不存在解
                    continue;
                }
                res = Math.min(res,1 + childNum);
            }
            dp[i] = res == Integer.MAX_VALUE ? -1 : res;
        }
        return dp[amount];
    }
}